package leetcode;
/*
* 珠宝最高价值
* */
public class Day12 {
    public int jewelleryValue(int[][] frame) {
    int m=frame.length;
    int n=frame[0].length;
    int[][] dp=new int[m+1][n+1];
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
        }
    }
    return dp[m][n];
    }
    /*
    * 下降路径最小和
    * */
    public static int minFallingPathSum(int[][] matrix) {
    int m=matrix.length;
    int n=matrix[0].length;
    int[][] dp=new int[m+1][n+2];
    int min= Integer.MAX_VALUE;
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            if (j==1){
                dp[i][j]= Math.min(dp[i-1][j+1],dp[i-1][j])+matrix[i-1][j-1];
            }else if(j==n){
                dp[i][j]=  Math.min(dp[i-1][j-1],dp[i-1][j])+matrix[i-1][j-1];
            }else {
                dp[i][j]=Math.min(Math.min(dp[i-1][j-1],dp[i-1][j+1]),dp[i-1][j])+matrix[i-1][j-1];
            }
        }
    }
   for (int i=1;i<=n;i++){
       if(dp[m][i]<min){
           min=dp[m][i];
       }
   }
   return min;
    }

    public static void main(String[] args) {
        int[][] arr=new int[3][3];
        arr[0][0]=-19;
        arr[0][1]=57;
       // arr[0][2]=3;
        arr[1][0]=-40;
        arr[1][1]=-5;
//        arr[1][2]=4;
//        arr[2][0]=7;
//        arr[2][1]=8;
//        arr[2][2]=9;
        int x=minFallingPathSum(arr);
        System.out.println(x);
    }
}
